package gold.digger;

import gold.utils.InputUtil;

import java.util.*;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC274 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution {
        public int hIndex(int[] citations) {
            if (citations == null || citations.length <= 0) return 0;

            Integer citationsWrapper[] = new Integer[citations.length];
            for (int i = 0; i < citations.length; i++) {
                citationsWrapper[i] = new Integer(citations[i]);
            }

            Arrays.sort(citationsWrapper);
            TreeMap<Integer, Integer> aboveCitationMap = new TreeMap<>();
            for (int citation : citationsWrapper) {
                if (aboveCitationMap.containsKey(citation)) {
                    aboveCitationMap.put(citation, aboveCitationMap.get(citation) + 1);
                } else {
                    aboveCitationMap.put(citation, 1);
                }
                updateCitation(aboveCitationMap, citation);
            }


            TreeSet<Integer> count = new TreeSet<>();
            for (Integer key : aboveCitationMap.descendingKeySet()) {
                count.add(Math.min(aboveCitationMap.get(key).intValue(), key.intValue()));
            }

            for (Integer key : count.descendingSet()) {
                return key;
            }

            return 0;
        }

        public void updateCitation(Map<Integer, Integer> aboveCitationMap, int citation) {
            for (Integer citationKey : aboveCitationMap.keySet()) {
                if (citationKey < citation) aboveCitationMap.put(citationKey, aboveCitationMap.get(citationKey) + 1);
                else break;
            }
        }
    }

    public void run() {
        Solution solution = new Solution();
//        int[] arr = InputUtil.toIntegerArray("[1,1]");
        int[] arr = InputUtil.toIntegerArray("[3,0,6,1,5]");
        System.out.println(solution.hIndex(arr));
    }

    public static void main(String[] args) throws Exception {
        LC274 an = new LC274();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
